#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
struct node{    int val;
		struct node *ptr;
	   };
struct node *first,*temp;

int pos,i;
int cnt,pos_p;
int size=0;
int flag;
int cntr;
int siz2,siz3;

//function to insert a number at a particular position
void insrt(struct node *temp,int num,int pos)
{ size=0;
  struct node *temp1;
  temp1=temp;
  while(temp1!=NULL)
	{ temp1=temp1->ptr;
	  size++;
	}
  if(pos<=size)
  	{struct node *new;
  	new=malloc(sizeof(struct node));
  	new->val=num;
 	 new->ptr=NULL;
 	 for(i=0;i<pos-1;i++)
		{ temp=temp->ptr;
		}
  	new->ptr=temp->ptr;
  	temp->ptr=new;
	}
  else
	{ printf("Enter valid position!!!");
	}
} 

//to append a number in the beginning of the list
struct node *append(struct node *temp,int num)
{ struct node *new;
  new=malloc(sizeof(struct node));
  new->val=num;
  new->ptr=temp;
  return new;
}

//appends a list of number in the dynamic list
struct node *extend(struct node *temp,int n,int a[n])
{ struct node *new;
  for(i=0;i<n;i++)
  	{ 
  	  new=malloc(sizeof(struct node));
  	  new->val=a[i];
  	  new->ptr=temp;
  	  temp=new;
	}
   return new;
}

//to delete a number from the dynamic list
struct node *delete(struct node *temp,int value)
{ struct node *cur,*pre;
  pre=malloc(sizeof(struct node));
  cur=malloc(sizeof(struct node));
  cur=temp;
  pre=NULL;
  while(cur!=NULL && cur->val!=value)
	{ pre=cur;
	  cur=cur->ptr;
  	}

  if(cur==NULL)	//if the number is not found
	{ printf("number not found...");		
	 return temp;
	}
  else if (pre==NULL)	//if the first number is the required number
	temp=temp->ptr;
  else
	{ pre->ptr=cur->ptr;
	  free(cur);
          return temp;
	}
}			


//pop function deletes a number from the list and prints the deleted number
struct node* pop(struct node *temp,int pos_p)
{  int k=0;
  struct node *cur,*n_cur;
  cur=NULL;
  n_cur=temp;
  if (pos_p==0)
	       {printf("\n The number deleted is %d",n_cur->val); 
		temp=(temp)->ptr;
	       }
  else
	{while( n_cur!=NULL && k!=pos_p)
	  { cur=n_cur;
	  n_cur=cur->ptr;
	  k++;
  	}
  	if(n_cur==NULL)
	{ printf("Enter valid position!!");
 	}
  	else
  	{ printf("\n The number deleted is %d",n_cur->val);
          cur->ptr=n_cur->ptr;
          free(n_cur);
          
	}
  	return temp;
	}
       	
}			

//returns the position of a number 
int indx(struct node *first_i,int n)
{ int pos=0;
  flag=0;
  while(first_i!=NULL)
	{ if(first_i->val==n)
		{ flag=1;
		  return pos;
		  break;
		}
	  else
		{ first_i=first_i->ptr;
		  pos++;
		}
	}
  if(flag==0)
	{ printf("number not in the list!! ");
	  return -1;
	}
}

//reversing a list
struct node* reverse( struct node *first )
{
    struct node *temp1,*pre;
    pre=NULL;
    while(first!= NULL) 
 	{  temp1=first->ptr;
           first->ptr=pre;
           pre=first;
           first = temp1;
        }
    return pre;
}

//sorts the number 
void sort(struct node *first_s,int cntr)
{ int temp_s;
  struct node *temp2_s;
  temp2_s=malloc(sizeof(struct node));
  temp2_s=first_s->ptr;
  if(cntr==0)		//sorting in increasing order
   {while(first_s->ptr!=NULL)
	{ while(temp2_s!=NULL)
		{ 
	  	  if((first_s->val) > (temp2_s->val))
			{ temp_s=first_s->val;
		  	  first_s->val=temp2_s->val;
		          temp2_s->val=temp_s;
 		        }
	  	  temp2_s=temp2_s->ptr;
		  
		}
	  first_s=first_s->ptr;
	  temp2_s=first_s->ptr;
	}
     }
  else if(cntr==1)		//sorting in decreasing order
   {while(first_s->ptr!=NULL)
	{ while(temp2_s!=NULL)
		{ 
	  	  if((first_s->val) < (temp2_s->val))
			{ temp_s=first_s->val;
		  	  first_s->val=temp2_s->val;
		          temp2_s->val=temp_s;
 		        }
	  	  temp2_s=temp2_s->ptr;
		  
		}
	  first_s=first_s->ptr;
	  temp2_s=first_s->ptr;
	}
     } 
   else
	{ printf("Wrong choice entered!!!");
	}

}
  

//counts and returns the occurence of a number in the list
int count(struct node *first,int n)
{struct node *temp_c;
 temp_c=first;
 cnt=0;
  while(temp_c!=NULL)
	{ if(temp_c->val==n)
		{cnt++;
		}
	  temp_c=temp_c->ptr;
	}
  return cnt;
}

//returns the size of the list
int siz(struct node *temp1)
{ siz2=0;
  while(temp1!=NULL)
	{ temp1=temp1->ptr;
	  siz2++;
	}
  return siz2;
}

//prints the numbers of the list
void show()
 { printf("\n List is:");
   struct node *first_show;
   first_show=malloc(sizeof(struct node));
   first_show=first;  
   while(first_show!=NULL)
	{ 
	  printf("\n %d",first_show->val);
          first_show=first_show->ptr;
	}
 }

int num,ch,i,n,pop_n;
char ans;
int* a;

void main()
{ first=malloc(sizeof(struct node));
  
  printf("Enter a number:");
  scanf("%d",&first->val);
  first->ptr=NULL;
  temp=first;
  printf("\t \t MENU");
  printf("\n 1. insert...");
  printf("\n 2. append...");
  printf("\n 3. extend...");
  printf("\n 4. delete...");
  printf("\n 5. pop...");
  printf("\n 6. count...");
  printf("\n 7. index...");
  printf("\n 8. sort...");
  printf("\n 9. reverse...");
  printf("\n 10. size...");
  printf("\n 11. display...");

  do
 {
  printf("\n Enter your choice:");
  scanf("%d",&ch);
  switch(ch)
		{ case 1:{     printf("Enter the number and position where you want to insert");
  			       scanf("%d %d",&num,&pos);
  			       insrt(first,num,pos);
			       show();

			  }
			  break;

		 case 2:{     printf("Enter the number you want to append");
  			      scanf("%d",&num);
  			      first=append(first,num);
			      show();

			  }
			  break;
		

		  case 3: {     printf("how many numbers do you want to enter?");
  				scanf("%d",&n);
				a=(int*) malloc(n*sizeof(int));
  				for(i=0;i<n;i++)
				{ printf("\n Enter:");
	  			  scanf("%d",&num);
	  			  a[i]=num;
				}
				first=extend(first,n,a);
				show();

			  }
			  break;
	
		case 4: { printf("\n Enter the number which you want to delete:");
  			  scanf("%d",&num);
			  first=delete(first,num);
			  show();
			 }
			  break;
	
		case 5: { printf("\n Enter the position from which you want to delete:");
  			  scanf("%d",&num);
			  first=pop(first,num);
			  
			  show();
			 }
			  break;

		 case 6: { printf("\n Enter the number which you want to count");
  			   scanf("%d",&num);
			   cnt=count(first,num);
			   printf("\n The number occurs: %d",cnt);
			  }
			  break;
		case 7:  {  printf("\n Enter the number whose index you want to search");
  			    scanf("%d",&num);
			    pos=indx(first,num);
			    printf("\n The number occurs at: %d",pos);
			    show();
			  }
			  break;
	
		case 8:{printf("\n You want to sort the list in increasing(0) or decreasing order(1)?");
  		        printf("\n Enter choice 0 or 1:");
  		        scanf("%d",&cntr);
			sort(first,cntr);
		        show();
		       }
			break;

		case 9:{first=reverse(first);
		        show();
		       }
			break;
		case 10:{siz3=siz(first);
			 printf("size of the list is: %d",siz3);
			}
			break;
		case 11:show();
			break;
		}
 printf("Do you want to perform more operations??");
 scanf("%s",&ans);
 }while(ans=='y' || ans=='Y');
  
}
